class Solution {
public:
    vector<string> Permutation(string str) {
        if(str.empty())
            return {};
        set<string> res;//使用set去除字符重复情况，以及将字符串按字典序排序(set默认从小到大排序)
        Perm(0,str,res);//递归
        return vector<string>({res.begin(),res.end()});//创建新vector，将set导入
    }
    void Perm(int pos,string str,set<string> &res){
        if(pos+1==str.length()){//pos+1长度与str相等时相当于固定好了一个字符串(之前位都固定了所以最后一位不需要固定)
            res.insert(str);
            return;
        }
        
        for(int i=pos;i<str.length();i++)//pos+1其实是固定一位的过程
        {
            swap(str[pos],str[i]);//遍历，用来搜索不同的情况
            Perm(pos+1,str,res);//固定一位
            swap(str[pos],str[i]);//因为想法中假设的全部替换情况均已最初情况开始思考的，所以回归成最初情况，便于思考
        }
    }
};